Maximal Lotteries

Maximal lotteries refers to a probabilistic voting system first considered by the French mathematician and social scientist Germain KrewerasG. Kreweras. ''Aggregation of preference orderings''. In Mathematics and Social Sciences I: Proceedings of the seminars of Menthon-Saint-Bernard, France (1–27 July 1960) and of Gösing, Austria (3–27 July 1962), pages 73–79, 1965. in 1965. The method uses preferential ballots and returns so-called maximal lotteries, i.e., probability distributions over the alternatives that are weakly preferred to any other probability distribution. Maximal lotteries satisfy the Condorcet criterion, the Smith criterion, reversal symmetry, polynomial runtime, and probabilistic versions of reinforcement,F. Brandl, F. Brandt, and H. G. Seedig
Consistent probabilistic social choice
Econometrica. 84(5), pages 1839-1880, 2016. participation,F. Brandl, F. Brandt, and J. Hofbauer
Welfare Maximization Entices Participation
Games and Economic Behavior. 14, pages 308-314, 2019. and independence of clones.

Maximal lotteries are equivalent to mixed maximin strategies (or Nash equilibria) of the symmetric zero-sum game given by the pairwise majority margins. As such, they have a natural interpretation in terms of electoral competition between two political parties. Laslier, J.-F. ''Interpretation of electoral mixed strategies'' Social Choice and Welfare 17: pages 283–292, 2000. Moreover, they can be computed using linear programming. The voting system that returns all maximal lotteries is axiomatically characterized as the only one satisfying probabilistic versions of population-consistency (a weakening of reinforcement) and composition-consistency (a strengthening of independence of clones). A social welfare function that top-ranks maximal lotteries is characterized using Arrow's independence of irrelevant alternatives and Pareto efficiency.F. Brandl and F. Brandt
Arrovian Aggregation of Convex Preferences
Econometrica. 88(2), pages 799-844, 2020. Maximal lotteries satisfy a strong notion of Pareto efficiency and a weak notion of strategyproofness.H. Aziz, F. Brandt, and M Brill
On the Tradeoff between Economic Efficiency and Strategyproofness
Games and Economic Behavior. 110, pages 1-18, 2018. In contrast to random dictatorship, maximal lotteries do not satisfy the standard notion of strategyproofness. Also, maximal lotteries are not monotonic in probabilities, i.e., it is possible that the probability of an alternative decreases when this alternative is ranked up. However, the probability of the alternative will remain positive. Laslier, J.-F. ''Tournament solutions and majority voting'' Springer-Verlag, 1997.

Maximal lotteries or variants thereof have been rediscovered multiple times by economists,G. Laffond, J.-F. Laslier, and M. Le Breton. ''The bipartisan set of a tournament game''. Games and Economic Behavior, 5(1):182–201, 1993. mathematicians,P. C. Fishburn. ''Probabilistic social choice based on simple voting comparisons''. Review of Economic Studies, 51(4):683–692, 1984.D. C. Fisher and J. Ryan. ''Tournament games and positive tournaments''. Journal of Graph Theory, 19(2):217–236, 1995. political scientists, philosophers,D. S. Felsenthal and M. Machover. ''After two centuries should Condorcet’s voting procedure be implemented?'' Behavioral Science, 37(4):250–274, 1992. and computer scientists. R. L. Rivest and E. Shen. An optimal single-winner preferential voting system based on game theory. In Proceedings of 3rd International Workshop on Computational Social Choice, pages 399–410, 2010.
In particular, the support of maximal lotteries, which is known as the ''essential set''B. Dutta and J.-F. Laslier. ''Comparison functions and choice correspondences''. Social Choice and Welfare, 16: 513–532, 1999. or the ', has been studied in detail.F. Brandt, M. Brill, H. G. Seedig, and W. Suksompong. ''On the structure of stable tournament solutions''. Economic Theory, 65(2):483–507, 2018.

Similar ideas appear also in the study of reinforcement learning and evolutionary biology to explain the multiplicity of co-existing species.B. Laslier and J.-F. Laslier. ''Reinforcement learning from comparisons: Three alternatives are enough, two are not'' Annals of Applied Probability 27(5): 2907–2925, 2017.Jacopo Grilli, György Barabás, Matthew J. Michalska-Smith and Stefano Allesina. ''Higher-order interactions stabilize dynamics in competitive network models'' Nature 548: 210-214, 2017.

Collective preferences over lotteries

The input to this voting system consists of the agents' ordinal preferences over outcomes (not lotteries over alternatives), but a relation on the set of lotteries can be constructed in the following way: if $p$ and $q$ are lotteries over alternatives, $p\succ q$ if the expected value of the margin of victory of an outcome selected with distribution $p$ in a head-to-head vote against an outcome selected with distribution $q$ is positive. In other words, $p\succ q$ if it is more likely that a randomly selected voter will prefer the alternatives sampled from $p$ to the alternative sampled from $q$ than vice versa. While this relation is not necessarily transitive, it does always contain at least one maximal element.

It is possible that several such maximal lotteries exist, but unicity can be proven in the case where the margins between any pair of alternatives is always an odd number. This is the case for instance if there is an odd number of voters who all hold strict preferences over the alternatives. Following the same argument, unicity holds for the original "bipartisan set" that is defined as the support of the maximal lottery of a tournament game.

Example

Suppose there are five voters who have the following preferences over three alternatives:
* 2 voters: $a\succ b\succ c$
* 2 voters: $b\succ c\succ a$
* 1 voter: $c\succ a\succ b$

The pairwise preferences of the voters can be represented in the following skew-symmetric matrix, where the entry for row $x$ and column $y$ denotes the number of voters who prefer $x$ to $y$ minus the number of voters who prefer $y$ to $x$.

$\begin \begin & & a\quad & b\quad & c\quad \\ \end \\ \begin a\\ b\\ c\\ \end \begin 0 & 1 & -1\\ -1 & 0 & 3\\ 1 & -3 & 0\\ \end \end$

This matrix can be interpreted as a zero-sum game and admits a unique Nash equilibrium (or minimax strategy) $p$ where $p(a)=3/5$, $p(b)=1/5$, $p(c)=1/5$. By definition, this is also the unique maximal lottery of the preference profile above. The example was carefully chosen not to have a Condorcet winner. Many preference profiles admit a Condorcet winner, in which case the unique maximal lottery will assign probability 1 to the Condorcet winner.

References

{{Reflist

External links

voting.ml
(website for computing maximal lotteries)
Pnyx - Practical Preference Aggregation
(voting tool that, among other methods, offers maximal lotteries)

Preferential electoral systems